package org.example.top41_80;

import java.util.Scanner;

public class main53 {
    //零钱兑换 输入：coins = [1, 2, 5], amount = 11 输出：3
    //思路：dp数组的含义：j元钱所需的最少个数
    // 双for 第一层选择哪个零钱  第二层选择从当前硬币面额到目标金额的所有金额 注意j <=amount！！！
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < coins.length; i++) {
            coins[i]=sc.nextInt();
        }
        int amount = sc.nextInt();
        int res=coinsChange(coins,amount);
        System.out.println(res);
    }

    private static int coinsChange(int[] coins, int amount) {
        int max=Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i]=max;
        }
        dp[0]=0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount ; j++) {
                if(dp[j-coins[i]]!=max){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}
